#!/usr/bin/env python
# encoding: utf-8
"""
@author: shura
@position: saber
@contact: 2209032305@qq.com
@file: stack_tree.py
@time: 2019/2/23 11:49
@desc:
"""

# Definition for singly-linked list.


class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def mergeTwoLists(self, l1, l2):
        """
        # 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        dimmy_node = ListNode(0)
        cur = dimmy_node
        while l1 or l2:
            if not l1:
                cur.next = l2
                break
            if not l2:
                cur.next = l1
                break
            if l1.val < l2.val:
                cur.next = l1
                cur = cur.next
                l1 = l1.next
                cur.next = None
            else:
                cur.next = l2
                cur = cur.next
                l2 = l2.next
                cur.next = None
        return dimmy_node.next

    def reverseList(self, head):
        """
        反转一个单链表。 递归
        :param head:
        :return:
        """
        if not head:
            return
        if not head.next:
            return head
        else:
            newhead = self.reverseList(head.next)
            head.next.next = head
            head.next = None
            return newhead

    def reverseList_opt(self, head):
        """
        反转一个单链表。 非递归
        定义pre 和cur轻松解决
        :param head:
        :return:
        """
        if not head: return
        pre = None
        cur = head
        while cur:
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp
        return cur

    def sortList(self, head):
        """
        在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
        使用 归并排序，先快慢指针找中点分两半，分到最后。然后递归归并排序
        :param head:
        :return:
        """
        if not head or not head.next: return head
        mid = self.get_mid(head)
        l = head
        r = mid.next
        mid.next = None
        return self.merge(self.sortList(l), self.sortList(r))

    def merge(self, p, q):
        temp = ListNode(0)
        cur = temp
        while p and q:
            if p.val < q.val:
                cur.next = p
                p = p.next
            else:
                cur.next = q
                q = q.next
            cur = cur.next
        if p:
            cur.next = p
        if q:
            cur.next = q
        return temp.next

    def get_mid(self, node):
        if not node:
            return node
        fast = node
        slow = node
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        return slow


a1 = ListNode(1)
a2 = ListNode(2)
a3 = ListNode(3)
b1 = ListNode(1)
b2 = ListNode(2)
b3 = ListNode(4)
a1.next = a2
a2.next = a3
b1.next = b2
b2.next = b3
s = Solution()
print(s.mergeTwoLists(a1, b1))